﻿public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
public class Solution
{
    public TreeNode MergeTrees(TreeNode t1, TreeNode t2)
    {
        // 其中一个二叉树为空
        if (t1 is null) return t2;
        if (t2 is null) return t1;
        
        // 后序遍历，合并二叉树
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.Push(t1);
        stack.Push(t2);
        TreeNode node1, node2;

        while (stack.Count > 0)
        {
            node2 = stack.Pop();
            node1 = stack.Pop();
            if (node1 is not null && node2 is not null)
            {
                stack.Push(node1);
                stack.Push(node2);
                stack.Push(null);
                stack.Push(null);
                
                if (node1.right is not null && node2.right is not null)
                {
                    stack.Push(node1.right);
                    stack.Push(node2.right);
                }
                
                if (node1.left is not null && node2.left is not null)
                {
                    stack.Push(node1.left);
                    stack.Push(node2.left);
                }
                
            }
            else if (node1 is null && node2 is null)
            {
                node2 = stack.Pop();
                node1 = stack.Pop();
                // 合并节点
                node1.val += node2.val;
                if (node1.left is null && node2.left is not null) node1.left = node2.left;
                if (node1.right is null && node2.right is not null) node1.right = node2.right;
            }
        }
        
        return t1;
    }

    public static void Main(string[] args)
    {
        int?[] root1 = [1, 3, 2, 5], root2 = [2, 1, 3, null, 4, null, 7];
        TreeNode t1 = CreateBinaryTree(root1);
        TreeNode t2 = CreateBinaryTree(root2);
        PreOrderPrint(t1);
        Console.WriteLine();
        PreOrderPrint(t2);
        Console.WriteLine();
        Solution solution = new Solution();
        TreeNode rootNode = solution.MergeTrees(t1, t2);
        PreOrderPrint(rootNode);
    }
    private static TreeNode CreateBinaryTree(int?[] root)
    {
        if (root is null || root.Length == 0 || root[0] is null)
        {
            return null;
        }

        Queue<TreeNode> queue = new Queue<TreeNode>();
        TreeNode rootNode = new TreeNode(root[0].Value);
        queue.Enqueue(rootNode);
        int i = 1;
        TreeNode node;
        bool flag;

        while (i < root.Length && queue.Count > 0)
        {
            flag = true;
            node = queue.Dequeue();
            if (root[i] is not null)
            {
                flag = false;
                node.left = new TreeNode(root[i].Value);
                queue.Enqueue(node.left);
            }

            i++;
            if (i >= root.Length) break;
            if (root[i] is not null)
            {
                flag = false;
                node.right = new TreeNode(root[i].Value);
                queue.Enqueue(node.right);
            }
            i++;

            if (flag)
            {
                queue.Enqueue(node);
            }
        }

        return rootNode;
    }

    
    private static void PreOrderPrint(TreeNode rootNode)
    {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        if (rootNode is not null) stack.Push(rootNode);
        TreeNode node;
        while (stack.Count > 0)
        {
            node = stack.Pop();
            Console.Write($"{node.val} ");
            if (node.right is not null) stack.Push(node.right);
            if (node.left is not null) stack.Push(node.left);
        }
    }
}